package 剑指Offer_day06;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class Offer_32_III {

    public List<List<Integer>> levelOrder(TreeNode root) {

        if (root==null){

            return new ArrayList<>();

        }

//        使用队列 保存每一层的节点 每一层都保存在一个数组中
        LinkedList<ArrayList<TreeNode>> linkedList = new LinkedList<>();

        //将头节点 放到对列中
        ArrayList<TreeNode> arrayList = new ArrayList<>();
        arrayList.add(root);
        linkedList.add(arrayList);

        //用来保存结果
        List<List<Integer>> result = new ArrayList<>();

        int corr = 1;
        //队列不为空
        while (!linkedList.isEmpty()){

            //从队列中 弹出一个集合 当前层的所有的节点
            ArrayList<TreeNode> list = linkedList.poll();

            //用于保存 当前层的value
            ArrayList<Integer> integers = new ArrayList<>();

            //用来保存 下一层的所有的节点
            ArrayList<TreeNode> treeNodes = new ArrayList<>();

            //开始遍历 当前层的节点
            for (TreeNode treeNode : list) {
                if(treeNode!=null){
                    integers.add(treeNode.val);
                    if (treeNode.left!=null)treeNodes.add(treeNode.left);
                    if (treeNode.right!=null)treeNodes.add(treeNode.right);
                }
            }

            //下一层的节点 放入队列
            if (!treeNodes.isEmpty())linkedList.add(treeNodes);

            //这一层的结果集合 放入集合  偶数层翻转
            if(corr%2==0){
                Collections.reverse(integers);
            }
            if(!integers.isEmpty()) result.add(integers);

            corr++;
        }

        return result;

    }

}
